package sort;

import java.util.Arrays;
import java.util.Random;

/**
 * Created With IntelliJ IDEA.
 * Descriptions:
 * User:Mr.Du
 * Date:2022/3/8
 * Time:17:13
 */
public class 堆排序 {

    public static void main(String[] args) {
        int[] arr = new int[10];
        Random r = new Random();
        for(int j = 0;j<10;j++){
            for(int i = 0;i<arr.length;i++){
                arr[i] = r.nextInt(50);
            }
            System.out.println("原数组: ");
            System.out.println(Arrays.toString(arr));
            smallHeapSort(arr);
            System.out.println("排序后的数组: ");
            System.out.println(Arrays.toString(arr));

        }

    }

    /**
     * 构建大顶堆
     * @param arr
     * @param len
     * @param i
     */
    public static void adjustBigHeap(int []arr, int i, int len){
        int tmp = arr[i];//先取出当前元素i
        for(int k = i * 2 + 1; k < len; k = k * 2 + 1){
            //从i结点的左子结点开始，也就是2i+1处开始
            //先找到左右结点最大的那个
            if(k + 1 < len && arr[k] < arr[k+1]){
                //如果左子结点小于右子结点，k指向右子结点
                k++;
            }
            //将最大子结点和父节点比较，
            //如果子节点大于父节点，将子节点值赋给父节点（不用进行交换）
            if(arr[k] > tmp){
                arr[i] = arr[k];
                //不交换的原因是：要在当前结点的所有孩子结点中，找出比当前结点值大的结点
                //用i记录当前最小值的位置
                i = k;
            }else{
                break;
            }
        }
        arr[i] = tmp;//将temp值放到最终的位置
    }

    /**
     * 1、构建一个大顶堆，然后将堆顶元素和最后一个元素交换，
     * 2、让数组长度减i(i就是循环次数)，重复步骤1
     * @param arr
     */
    public static void smallHeapSort(int[] arr) {
        //建立初始堆
        for (int i = (arr.length - 1) / 2; i >= 0; i--) {
            adjustBigHeap(arr, i, arr.length);
        }
        System.out.println("初始堆为: ");
        System.out.println(Arrays.toString(arr));
        //边输出堆顶边调整
        for (int j = arr.length - 1; j > 0; j--) {
            //将堆顶元素与末尾元素进行交换
            swap(arr, 0, j);
            //重新对堆进行调整
            adjustBigHeap(arr, 0, j);

        }
    }
    public static void swap(int []arr,int a ,int b){
        int temp=arr[a];
        arr[a] = arr[b];
        arr[b] = temp;
    }

}
